package com.lw.leetcode.hash.b;

import java.util.*;

/**
 * create by idea
 * 380. O(1) 时间插入、删除和获取随机元素
 * 剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器
 *
 * @author lmx
 * @version 1.0
 * @date 2021/12/30 18:11
 */
public class RandomizedSet {


    public static void main(String[] args) {
        RandomizedSet test = new RandomizedSet();


        // ["RandomizedSet","insert","insert","remove","insert","remove","getRandom"]
        //[[],[0],[1],[0],[2],[1],[]]


        test.insert(0);
        test.insert(1);
        System.out.println(test.list);
        test.remove(0);
        System.out.println(test.list);
        test.insert(2);
        System.out.println(test.list);
        test.remove(1);
        System.out.println(test.list);
        int random = test.getRandom();
        System.out.println(random);

    }

    private Map<Integer, Integer> map;
    private List<Integer> list;
    private int index = -1;

    public RandomizedSet() {
        map = new HashMap<>();
        list = new ArrayList<>();
    }

    public boolean insert(int val) {
        if (map.containsKey(val)) {
            return false;
        }
        index++;
        map.put(val, index);
        if (list.size() > index) {
            list.set(index, val);
        } else {
            list.add(val);
        }
        return true;
    }

    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false;
        }
        list.set(map.get(val), list.get(index));
        map.put(list.get(index), map.get(val));
        map.remove(val);
        index--;
        return true;
    }

    public int getRandom() {
        int i = new Random().nextInt(index + 1);
        return list.get(i);
    }

}
